NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/8171

Text File | 1996-08-05 | 3.1 KB | 143 lines

Newsgroups: comp.lang.c
Path: news.dcs.warwick.ac.uk!not-for-mail
From: [e-mail] (Daniel Castillo Molero)
Subject: Re: Permutations
X-Nntp-Posting-Host: cray
Message-ID: <[e-mail]>
Sender: [e-mail] (Network News)
Organization: Department of Computer Science, Warwick University, England
References: <[e-mail]> <4grvqb$[e-mail]>
Date: Sat, 2 Mar 1996 03:41:12 GMT

In article <4grvqb$[e-mail]> Matthias Dittrich <matti> writes:
>[e-mail] (David Turner) wrote:
>>Does anyone know of an algorithm that works out the different purmutations
>>of ordering a number of objects? Not calculating how many there are, but
>>actaully working out (quickly?) what they permutations are!
>>
>>        eg. permutations of objects A, B and C:
>>
>>                A B C   B A C   C A B
>>                A C B   B C A   C B A
>>
>>Any help would be greatly appreciated.
>>
>>David
>>
>Here is one I've just written:
>
>#include <stdio.h>
>#include <string.h>
>
>#define MAX_PERM 8
>
>void permfunc(unsigned long i, char* str);
>void do_perm(char* str);
>
>int main(int argc, char** argv)
>{
>  unsigned long n = 2, i;
>  char str[MAX_PERM];
>
>    /* do some essential checks */
>  if(argc < 2) return 1;
>
>  sscanf(argv[1], "%lu", &n);
>
>  if(n >= MAX_PERM)
>  {
>    n = MAX_PERM - 1;
>    fprintf(stderr, "number too big, set to %d\n", n);
>  }
>
>    /* initialize the string to show permutations */
>  for(i=0; i<n; i++)
>  {
>    str[i] = 'A' + i;
>  }
>  str[n] = '\0';
>
>    /* call permfunc with starting level 0 */
>  permfunc(0, str);
>
>  return 0;
>}
>
>void permfunc(unsigned long i, char* str)
>{
>  char s[MAX_PERM];
>  char *t = s + i;
>  char *u = str + i;
>
>    /* check if at least two characters are in the string */
>  if(*u && *(u + 1))
>  {
>    strcpy(s, str);
>
>    permfunc(i + 1, s);
>    u = t + 1;
>
>      /* the number of characters in the string is the number of
>         permutations to do */
>    while(*u)
>    {
>        /* after the permutation has been done
>           call this function recursively, increasing the starting level */
>      do_perm(t);
>      permfunc(i + 1, s);
>      u++;
>    }
>  }
>  else
>  {
>    printf("%s\n", str);
>  }
>}
>
>  /* do the permutation on a string */
>void do_perm(char* str)
>{
>  char *s, *t, c;
>
>  s = t = str;
>  t++;
>
>    /* save first char */
>  c = *s;
>    /* move all chars one position to the left */
>  while(*t) *s++ = *t++;
>    /* set the last char */
>  *s = c;
>}
>
>I think there may be faster ways to do it, but it works.
>
>Good luck,
>Matthias
>


I'm very interested in using this program to generate permutations, but when
I compile it with 'gcc program.c'  and then run it I get a strange result.
For example, if the executable is called permut, and I enter

   permut a b c d

I get as output

   AB
   BA

I am a beginner in c and would appreciate very much if you could tell me
what I am doing wrong.

Thank you for reading this message

danny


--
* Daniel Castillo.  [e-mail] *